#ifndef __LOCK_FREE_QUEUE__
#define __LOCK_FREE_QUEUE__

#include "cpp_framework.h"
#include <iostream>

using namespace std;
using namespace CMDR;

template<typename T>
class LockFreeQueue {
protected:

	class Node : public HazardMemory::Object {
	public:
		T								value;
		AtomicReference<Node>	next;

		Node(T in_value) : value(in_value), next(null) { }

		virtual bool isValid() { return true; }
		virtual HazardMemory::Object* getNextValid(const int indx) {
			return next.get();
		}

		virtual HazardMemory::Object* getNextValid(const int indx, int& flag) {
			flag = 0;
			return next.get();
		}
	};

	AtomicReference<Node> head;
	AtomicReference<Node> tail;

public:
	LockFreeQueue() {
		Node* sentinel = new Node(null);
		head.set(sentinel);
		tail.set(sentinel);
	}

	void enq(const T item) {
		HazardMemory::Ptr<Node> last;
		HazardMemory::Ptr<Node> next;
		Node* node = new Node(item);			// allocate & initialize new node

		while (true) {											// keep trying
			last = tail;										// read tail
			next.extractNext(last,0);							// read next
			if (last.getReference() == tail.get()) {	// are they consistent?
				if (null == next.getReference()) {
					if (last->next.compareAndSet(next.getReference(), node)) {
		 				tail.compareAndSet(last.getReference(), node);
						return;
					}
				} else {
					tail.compareAndSet(last.getReference(), next.getReference());
				}
			}
		}
	}

	T deq() {
		HazardMemory::Ptr<Node>	first;
		HazardMemory::Ptr<Node> last;
		HazardMemory::Ptr<Node> next;

		while (true) {
			first = head;
			last = tail;
			next.extractNext(first,0);
			if (first.getReference() == head.get()) {					// are they consistent?
				if (first.getReference() == last.getReference()) {	// is queue empty or tail falling behind?
					if (null == next.getReference()) {					// is queue empty?
						return null;
					}
					tail.compareAndSet(last.getReference(), next.getReference()); // tail is behind, try to advance
				} else {
					T value = next->value;									// read value before dequeuing
					if (head.compareAndSet(first.getReference(), next.getReference())) {
						first.retire();
						return value;
					}
				}
			}
		}
	}

	T peek() {
		HazardMemory::Ptr<Node> first;
		HazardMemory::Ptr<Node> next;

		first = head;
		next.extractNext(first,0);
		if (null != next.getReference()) {
			return next.getReference()->value;
		}
		return null;
	}
};

#endif
